package 单周赛.history;

import java.util.PriorityQueue;

/**
 *
 */
public class 第327场单周赛 {

    public static void main(String[] args) {

        System.out.println(maxKelements(new int[]{1, 10, 3, 3, 3}, 3));

        System.out.println(isItPossible("ac", "b"));

    }

    public int maximumCount(int[] nums) {
        int fu = 0, zhen = 0;
        for (int num : nums) {
            if (num > 0) {
                zhen++;
            }
            if (num < 0) {
                fu++;
            }
        }
        return Math.max(fu, zhen);
    }

    /**
     * 贪心+优先队列
     * 每次选择数组中最大的元素
     */
    public static long maxKelements(int[] nums, int k) {
        long maxScore = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);

        for (int num : nums) {
            priorityQueue.add(num);
        }

        while (k-- > 0) {
            Integer poll = priorityQueue.poll();
            maxScore += poll;
            priorityQueue.add(poll % 3 == 0 ? poll / 3 : poll / 3 + 1);
        }

        return maxScore;
    }

    /**
     * 统计字符数量+模拟+回溯
     */
    public static boolean isItPossible(String word1, String word2) {
        int[] record1 = new int[26];
        int[] record2 = new int[26];
        for (char c : word1.toCharArray()) {
            record1[c - 'a']++;
        }
        for (char c : word2.toCharArray()) {
            record2[c - 'a']++;
        }

        for (int i = 0; i < record1.length; i++) {
            for (int j = 0; j < record2.length; j++) {
                if (record1[i] > 0 && record2[j] > 0) {
                    record1[i]--;
                    record1[j]++;
                    record2[i]++;
                    record2[j]--;

                    if (isDiffCount(record1, record2)) {
                        return true;
                    }

                    record1[i]++;
                    record1[j]--;
                    record2[i]--;
                    record2[j]++;
                }
            }
        }

        return false;
    }

    private static boolean isDiffCount(int[] record1, int[] record2) {
        int cnt = 0;
        for (int i = 0; i < record1.length; i++) {
            if (record1[i] > 0) {
                cnt++;
            }
            if (record2[i] > 0) {
                cnt--;
            }
        }
        return cnt == 0;
    }

}
